package com.mango.leet.code.easy;

/**
 * 997. 找到小镇的法官
 * @Author: mango
 * @Date: 2022/4/27 9:04 下午
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
 *
 * 如果小镇法官真的存在，那么：
 *
 * 小镇法官不会信任任何人。
 * 每个人（除了小镇法官）都信任这位小镇法官。
 * 只有一个人同时满足属性 1 和属性 2 。
 * 给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
 *
 * 如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 2, trust = [[1,2]]
 * 输出：2
 * 示例 2：
 *
 * 输入：n = 3, trust = [[1,3],[2,3]]
 * 输出：3
 * 示例 3：
 *
 * 输入：n = 3, trust = [[1,3],[2,3],[3,1]]
 * 输出：-1
 *  
 * 提示：
 *
 * 1 <= n <= 1000
 * 0 <= trust.length <= 104
 * trust[i].length == 2
 * trust 中的所有trust[i] = [ai, bi] 互不相同
 * ai != bi
 * 1 <= ai, bi <= n
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-town-judge
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC997 {
    class Solution {
        public int findJudge2(int n, int[][] trust) {
            if(trust.length == 0 && n == 1){
                return 1;
            }
            Graph graph = Graph.createGraph(trust);
            // 大根堆，按顶点入度排序
            PriorityQueue<Vertex> pq = new PriorityQueue<>((o1, o2) -> o2.in - o1.in);
            for(Vertex vertex : graph.vertexs.values()){
                pq.offer(vertex);
            }
            Vertex judgeVertex = pq.poll();
            // 最大入度的顶点出度为0且入度=n-1，则找到法官
            return judgeVertex != null && judgeVertex.out == 0 && judgeVertex.in == n -1  ? Integer.valueOf(judgeVertex.value) : -1;
        }

        public int findJudge(int n, int[][] trust) {
            if(trust.length == 0 && n == 1){
                return 1;
            }
            Graph graph = Graph.createGraph(trust);
            // 找到入度最大的顶点
            Vertex judgeVertex = null;
            for(Vertex vertex : graph.vertexs.values()){
                if(judgeVertex == null){
                    judgeVertex = vertex;
                }else{
                    if(judgeVertex.in < vertex.in){
                        judgeVertex = vertex;
                    }
                }
            }
            // 最大入度的顶点出度为0且入度=n-1，则找到法官
            return judgeVertex != null && judgeVertex.out == 0 && judgeVertex.in == n -1  ? Integer.valueOf(judgeVertex.value) : -1;
        }
    }
}

class Graph {
    // 顶点集 - 邻接表
    public HashMap<String,Vertex> vertexs;
    // 边集
    public Set<Edge> edges;

    public Graph() {
        this.vertexs = new HashMap<>();
        this.edges = new HashSet<>();
    }

    /**
     * trust = [[1,3],[2,3]]
     * @param trust
     * @return
     */
    public static Graph createGraph(int[][] trust){
        Graph graph = new Graph();
        for(int[] arr : trust){
            String from = arr[0] + "";
            String to = arr[1] + "";
            int weight = 1;
            if(!graph.vertexs.containsKey(from)){
                graph.vertexs.put(from,new Vertex(from));
            }
            if(!graph.vertexs.containsKey(to)){
                graph.vertexs.put(to,new Vertex(to));
            }
            Vertex fromVertex = graph.vertexs.get(from);
            Vertex toVertex = graph.vertexs.get(to);
            Edge edge = new Edge(weight,fromVertex,toVertex);
            fromVertex.nexts.add(toVertex);
            fromVertex.out++;
            toVertex.in++;
            fromVertex.edges.add(edge);
            if(!graph.edges.contains(edge)){
                graph.edges.add(edge);
            }
        }
        return graph;
    }
}
// 顶点
class Vertex{
    // 名称，值
    public String value;
    // 入度
    public Integer in;
    // 出度
    public Integer out;
    // 相邻的顶点集合
    public Set<Vertex> nexts;
    // 边集合
    public Set<Edge> edges;

    public Vertex(String value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        this.nexts = new HashSet<>();
        this.edges = new HashSet<>();
    }
}
// 边
class Edge{
    // 权重
    public int weight;
    // 出发顶点
    public Vertex from;
    // 到达顶点
    public Vertex to;
    public Edge(int weight, Vertex from, Vertex to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}
